给出一个图 G(V,E) ,图上有 n 个点,m 条边,所有的边都是无向边。
最开始,也就是第 0 天的时候,这 n 个点中有一个点 v 感染了病毒,之后的每一天,凡是感染病毒的点都会向它的邻居点传播病毒。经过了 t 天之后,得到了感染病毒的点集 S 。要求找出第 0 天感染病毒的点 v 。如果 v 有很多不同的答案,把它们都找出来。
数据范围: , ,
给出一个图 G(V,E) ,图上有 n 个点,m 条边,所有的边都是无向边。
第一行两个数n,m,接下来有m行,每行两个数u,v,表示点u,v之间有一条无向边。接下来一行两个数k,t,其中k表示集合S的大小。最后一行k个数,集合S中的元素。输入的图可能有自环和重边,输入保证S中的数互不相同。
输出一行,如果不存在这样的v,输出-1。
否则输出所有可能的v,按照从小到大的顺序输出,数字之间用空格隔开,不要在行末输出多余的空格。
4 3 3 2 1 2 1 4 3 2 4 2 1
4
第0天,第1天,第2天感染病毒的点如图
from collections import defaultdict n, m = map(int, input().split()) # n个点,m条边 d = defaultdict(set) # 用d存储图,用set去重 for _ in range(m): p1, p2 = map(int, input().split()) d[p1].add(p2) d[p2].add(p1) k, t = map(int, input().split()) # s大小为k,共t天 s = set(map(int, input().split())) # s为最终感染情况 res = [] def check(v): # BFS搜索,检查v点在t天后感染情况是否与符合要求 q = [v] infected = set([v]) # infected记录已经感染的地区 for i in range(t): if not q: break for j in range(len(q)): # 每天找出新增的感染地区 tmp = q.pop(0) for node in d[tmp]: if node not in infected: q.append(node) infected.add(node) if infected == s: # 如果感染情况与s一致,说明v符合要求,加入res res.append(v) for v in s: # 遍历s中每个点,检查是否符合要求 check(v) if not res: print(-1) else: print(' '.join(list(map(str,res))))